package _08_DFS_BFS;

import java.util.ArrayList;
import java.util.List;

public class _51_N皇后 {

    public static void main(String[] args) {

        _51_N皇后 v = new _51_N皇后();

        List<List<String>> lists = v.solveNQueens(4);

        for (List<String> list : lists) {
            System.out.println(list);
        }

    }

    private List<List<String>> results = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {

        // 存放已经选取的皇后
        List<int[]> visited = new ArrayList<>();
        dfs(n, visited, new ArrayList<>());
        return results;
    }

    private void dfs(int n, List<int[]> visited, List<String> list) {
        if (visited.size() == n) {
            results.add(new ArrayList<>(list));
            return;
        }

        for (int col = 0; col < n; col++) {
            int row = visited.size();
            // 判断是否能存放当前元素
            boolean isSuccess = true;
            for (int[] ints : visited) {
                int visRow = ints[0];
                int visCol = ints[1];
                // 竖直方向
                if (visCol == col) {
                    // 跳过
                    isSuccess = false;
                    break;
                } else if (Math.abs(row - visRow) == Math.abs(col - visCol)) {
                    // 斜线
                    isSuccess = false;
                    break;
                }
            }

            if (isSuccess) {
                // 尝试存放元素
                visited.add(new int[]{visited.size(), col});
                // 构造数据
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < n; j++) {
                    if (col == j) {
                        sb.append("Q");
                        continue;
                    }
                    sb.append(".");
                }
                list.add(sb.toString());
                dfs(n, visited, list);
                // 回溯
                visited.remove(visited.size() - 1);
                list.remove(list.size() - 1);
            }
        }
    }

}
